package cn.oder.insert;

import cn.oder.Sorted;
import cn.oder.SortedBase;
import cn.oder.enums.Sore;

import java.util.ArrayList;
import java.util.List;

/**
 * 类简介: 直接插入排序
 * 从第二个位置开始一次和前面元素比较
 * 时间复杂度是O（n^2）,在基本有序的情况下为O(n),时间复杂度为O(1) 稳定的
 *
 * @Author: ShangGuan
 * @Time: 2024/05/16
 **/
public class InsertSortsDirectly extends SortedBase implements Sorted {

    public InsertSortsDirectly(Sore sore, List<Integer> arr) {
        super(sore, arr);
    }

    public InsertSortsDirectly(List<Integer> arr) {
        super(arr);
    }

    @Override
    public  List<Integer> sort() {
        int n = arr.size();
        for (int i = 1; i < n; ++i) {
            int key = arr.get(i);
            int j = i - 1;
            // 将 arr[0..i-1] 中大于 key 的元素都向后移动一个位置
            if (sore.equals(Sore.ASC)) {
                while (j >= 0 && arr.get(j) < key) {
                    arr.set(j + 1, arr.get(j));
                    j = j - 1;
                }
            }
            if (sore.equals(Sore.DESC)) {
                while (j >= 0 && arr.get(j) > key) {
                    arr.set(j + 1, arr.get(j));
                    j = j - 1;
                }
            }
            arr.set(j + 1, key);
        }
        return new ArrayList<>(arr);

    }



}
